import java.util.HashSet;
import java.util.Random;

public class Main {
    static Random rn = new Random(System.currentTimeMillis());
    public static int getRandomInt(int i){
        return Math.abs(rn.nextInt())%i + 1;
    }

    public String generateStr() {
        int len = getRandomInt(7);
        String str = "";
        for (int i=0;i<len;i++){
            str += (char)(rn.nextInt(26) + 'a');
        }
        return str;
    }

    public void test(){
        String str = generateStr();
        testWithStr(str);
    }

    public void testCustomized(){
        String[] test = {"ABCABCA", "", "ABCDEFGH", "AABBCCDD", "A", "ABCDDEFA"};
        for(int i = 0; i<test.length;i++){
            testWithStr(test[i]);
        }
    }

    public void testWithStr(String str){
        Solution solution = new Solution();

        HashSet<String> expected = ermutations(str);
        HashSet<String> actual = solution.ermutations(str);

        if(str==""){
            if (actual.size()!= 0){
                throw new RuntimeException("Should return new HashSet()<String> for empty input");
            }
        }
        else if(!actual.equals(expected)){
            String msg = "Test Failed\n";
            msg += "Input:" + str + "\n";
            msg += "Expected:" + expected + "\n";
            msg += "Actual:" + actual;
            throw new RuntimeException(msg);
        }
    }

    public static void main(String[] args) {
        try {
            Main main = new Main();
            for (int i = 0; i < 20; i++) {
                main.test();
            }
            main.testCustomized();
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            System.exit(-1);
        }
    }

    public HashSet<String> ermutations(String str) {
        // If string is empty
        if (str.length() == 0) {

            // Return an empty arraylist
            HashSet<String> empty = new HashSet<>();
            empty.add("");
            return empty;
        }

        // Take first character of str
        char ch = str.charAt(0);

        // Take sub-string starting from the
        // second character
        String subStr = str.substring(1);

        // Recurvise call
        HashSet<String> prevResult = ermutations(subStr);

        // Store the generated permutations
        // into the resultant arraylist
        HashSet<String> Res = new HashSet<>();

        for (String val : prevResult) {
            for (int i = 0; i <= val.length(); i++) {
                Res.add(val.substring(0, i) + ch + val.substring(i));
            }
        }

        Res.remove("");

        // Return the resultant arraylist
        return Res;
    }
}
